#include <iostream>
#include <list>
#include <stdlib.h>
#include <string.h> // C string, not C++ string
using namespace std;

#include "grasp.h"
#include "func_generales.h"

#define MAX_ATTEMPT 50
#define MAX_LOOP 1000

int contadorCambios = 0;

pair<Graph*, PathMatrix*>* Construct(Graph* G, Graph* G_part, PathMatrix* P_part, int k);
pair<int, int>* mij_greater_than_zero(list<pair<int, int>*> *& lst, int** M, int size);

Path * GetPathCostZeroAccordingG(Graph * G, list<Path*>* Lp) {
    for (list< Path* >::iterator it = Lp->begin(); it != Lp->end(); ++it)
        if (G->CostPath(*it) == 0) return (*it);

    return NULL;
};

int GeneralUpdateMatrix(Graph *G_part, PathMatrix * PM, Path * p, int i, int j) {
    Path * sub_path;

    for (list<int>::iterator it = p->path->begin(); it != p->path->end(); ++it) {
        int node = (*it);
        if (G_part->IsTerminal(node) && node != i && node != j) {

            sub_path = p->SubPath(i, node);
            if (GetMatrix(G_part->R, i, node) > 0 && PM->IsNodeDisjointTo(sub_path, i, node)) {
                PM->Add(sub_path, i, node);
                DecreaseMatrix(G_part->R, i, node);
                //PrintPath(sub_path);
                //cout << "1: (i, k) " << "("<< i+1 << ", "<< node+1 << ")  ";
                //PrintPath(p, sub_path);
                //cout << "[ConstructGreedyRandomizedSolution][GeneralUpdateMatrix][INFO]: Entre " << "("<< i+1 << ", "<< j+1 << ")" << endl;
            } else
                delete sub_path;

            sub_path = p->SubPath(node, j);
            if (GetMatrix(G_part->R, node, j) > 0 && PM->IsNodeDisjointTo(sub_path, node, j)) {
                PM->Add(sub_path, node, j);
                DecreaseMatrix(G_part->R, node, j);
                //PrintPath(sub_path);
                //cout << "2: (k, j) " << "("<< node+1 << ", "<< j+1 << ")  ";
                //PrintPath(p, sub_path);
                //cout << "[ConstructGreedyRandomizedSolution][GeneralUpdateMatrix][INFO]: Entre " << "("<< i+1 << ", "<< j+1 << ")" << endl;
            } else
                delete sub_path;
        }
    }

    return 0;
};

pair<Graph*, PathMatrix*> * ConstructGreedyRandomizedSolution(Graph * Problem, int k) {
    Graph * G_part = new Graph(Problem->sizeG);
    PathMatrix * PM;
    pair<Graph*, PathMatrix*> * ret;
    int cant_loop = 0;

    PM = new PathMatrix(Problem->sizeG);

    //Init G_part
    for (int i = 0; i < Problem->sizeG; i++) {
        G_part->W[i] = Problem->W[i];
        G_part->_T[i] = Problem->_T[i];
        if (G_part->_T[i]) G_part->actived_node[i] = 1;

        for (int j = i; j < Problem->sizeG; j++) {
            G_part->C[i][j] = Problem->C[i][j];
            G_part->E[i][j] = 0;
            G_part->R[i][j] = Problem->R[i][j];
        }
    }
    G_part->T = new list<int>(*Problem->T); // hiper chancho!

RETRY:
    ret = Construct(Problem, G_part, PM, k);
    if (!ret) {
        cant_loop++;
        if (cant_loop < MAX_LOOP)
            goto RETRY;
        else
            cout << "[ConstructGreedyRandomizedSolution][INFO]: Not found feasible solution" << endl;
    }

    delete G_part;
    delete PM;

    return ret;
};

pair<Graph*, PathMatrix*> * Construct(Graph* G_problem, Graph* G_part, PathMatrix* P_part, int k) {
    list<pair<int, int>*> * mij_to_process = NULL;
    pair<int, int>* ij = NULL;
    // Es una copia para mantener P para poder reinicializar en caso de que se estanque el algoritmo
    PathMatrix* P_aster;
    list<Path*>* Lp;
    Graph* G_aster, * G_problem_aster;
    Path * p;
    bool ExistAijGreaterThanMaxAttempt = false;

    int** A = new int*[G_problem->sizeG];
    //A es una matriz dinaica, memcpy() pide array de memoria no se permite el doble acceso A[i][j] (no es una matriz)
    for (int i = 0; i < G_problem->sizeG; i++) {
        A[i] = new int[G_problem->sizeG];
        for (int j = i; j < G_problem->sizeG; j++)
            A[i][j] = 0;
    }

    // Copio para poder reestablecer en caso de error
    P_aster = new PathMatrix(P_part);
    G_aster = new Graph(G_part);
    G_problem_aster = new Graph(G_problem);

    while (!ExistAijGreaterThanMaxAttempt && (ij = mij_greater_than_zero(mij_to_process, G_aster->R, G_problem_aster->sizeG))) {

        // Esto aca es un buen pire para no sumar orden en restablecimeintos, ademas de resolver otros probelmas
        // que habian (mietras calulo C arreglo lo que rimpi, no sumo orden)
        for (int i = 0; i < G_problem->sizeG; i++) {

            G_problem_aster->actived_node[i] = G_problem->actived_node[i];

            if (G_aster->actived_node[i])
                G_problem_aster->W[i] = 0;
            else
                G_problem_aster->W[i] = G_problem->W[i];

            for (int j = i; j < G_problem->sizeG; j++) {
                G_problem_aster->E[i][j] = G_problem->E[i][j];
                if (G_aster->actived_node[i] && G_aster->actived_node[j] && G_aster->E[i][j])
                    G_problem_aster->C[i][j] = 0;
                else
                    G_problem_aster->C[i][j] = G_problem->C[i][j];
            }
        }
        G_problem_aster->SubstractWithoutExtremes((*P_aster)[ij->first][ij->second]);
        Lp = G_problem_aster->GetKPathsBetween(ij->first, ij->second, k, G_problem_aster->diameter);
        //G_problem->subLista_graph_viz(Lp, ij->first, ij->second, "GetKPathBetween");
        if (Lp->empty()) {
            A[ij->first][ij->second]++;

            if (A[ij->first][ij->second] < MAX_ATTEMPT) {
                DeleteListPath((*P_aster)[ij->first][ij->second]);
                (*P_aster)[ij->first][ij->second] = ClearCopy((*P_part)[ij->first][ij->second]);
                G_aster->R[ij->first][ij->second] = G_part->R[ij->first][ij->second];
                mij_to_process->push_front(ij);
            } else {
                ExistAijGreaterThanMaxAttempt = true;
                delete ij;
            }
        } else {
            if (!(p = GetPathCostZeroAccordingG(G_aster, Lp))) {
                p = SelectRandom(Lp);
                G_aster->Add(p);
            }
            P_aster->Add(p, ij->first, ij->second);
            (G_aster->R[ij->first][ij->second])--;
            GeneralUpdateMatrix(G_aster, P_aster, p, ij->first, ij->second);
            if ((G_aster->R[ij->first][ij->second]) > 0) {
                mij_to_process->push_front(ij);
            } else {
                delete ij;
            }
        }
        DeleteListPath(Lp);
    }


    if (ExistMiiGreaterThanZero(G_aster->R, G_problem->sizeG) || Uncoordinated(G_aster, P_aster)) {
        //cout << "444444444" << endl;
        delete G_aster;
        //cout << "555555555" << endl;
        delete P_aster;
        //cout << "555555555BBBBBBBBBBBBBB" << endl;
        DeleteMatrix(A, G_problem->sizeG);
        //cout << "888888888" << endl;
        delete G_problem_aster;
        //cout << "666666666" << endl;
        DeleteListPairInt(mij_to_process);
        //cout << "4444444444" << endl;
        return NULL;
    }

    //cout << "555555555BBBBBBBBBBBBBB" << endl;
    DeleteMatrix(A, G_problem->sizeG);
    delete G_problem_aster;


    //cout << "555555555555555" << endl;
    return new pair<Graph*, PathMatrix*>(G_aster, P_aster);
};

pair<int, int>* mij_greater_than_zero(list<pair<int, int>*> *& lst, int** M, int size) {
    pair<int, int>* ij;

    //cout << "33333333" << endl;
    if (!lst) {
        //cout << "444444444" << endl;
        lst = new list<pair<int, int>*>();

        for (int i = 0; i < size; i++) // Filas
            for (int j = i; j < size; j++) // Columnas, recordar: son matrices triangulares superiores
                if (M[i][j] > 0) {
                    lst->push_front(new pair<int, int>(i, j));
                    //cout << "Edge " << "(" << i << ", " << j << ")" << endl;
                }
    }
    //cout << "55555555" << endl;

    while (!lst->empty()) {
        ij = SelectRandom(lst); // retorna un par aleatorio tomado de lst, lo elimina de la lista
        if (M[ij->first][ij->second] > 0) {
            //cout << "6666666666" << endl;
            return ij;
        }
        delete ij;
    }

    //cout << "777777777777" << endl;
    delete lst;
    lst = NULL;
    return NULL;
}

/////////////////////////////////////////////////////////////////////////////////////////////////////////
// --------- Comienza la fase de busqueda -----------------
//----  SEARCH LOCAL PATH ---------------------
////////////////////////////////////////////////////////////////////////////////////////////////////////

list<Path*> * Xp(PathMatrix * PM, Path * p) {

    list<Path*> * l_paths = new list<Path*>();

    // Calculo de V/Xp
    for (int i = 0; i < PM->sizeP; i++) {
        for (int j = i; j < PM->sizeP; j++) {
            if ((PM->Contains(p, i, j))) {
                for (list<Path*>::iterator it = PM->P[i][j]->begin(); it != PM->P[i][j]->end(); ++it) {
                    l_paths->push_front(*it);
                }
            }
        }
    }

    return l_paths;
}

int LocalSearchKeyPath(Graph * G_problem, Graph *& G_sol, PathMatrix *& P_sol) {

    Graph * H = new Graph(G_problem);
    bool need_update = true;
    Path * p, * p_techo;
    int u, v;
    list<Path*> * Lp;
    list<Path *> * l_paths;
    list<Path*> * key_path_list;

    while (need_update) {
        need_update = false;
        key_path_list = G_sol->KeyPathDescomposition();
        while (!need_update && !key_path_list->empty()) {
            p = SelectRandom(key_path_list); // Selecciona y borra de la lista
            u = p->path->front();
            v = p->path->back();

            // Esto aca es un buen pire para no sumar orden en restablecimeintos, ademas de resolver otros probelmas
            // que habian (mietras calulo C arreglo lo que rimpi, no sumo orden)
            G_sol->SubstractWithoutExtremes(p); // es necesario quitar p a G_sol para recalcular C
            for (int i = 0; i < G_problem->sizeG; i++) {
                H->actived_node[i] = G_problem->actived_node[i];
                if (G_sol->actived_node[i])
                    H->W[i] = 0;
                else
                    H->W[i] = G_problem->W[i];
                for (int j = i; j < G_problem->sizeG; j++) {
                    H->E[i][j] = G_problem->E[i][j];
                    if (G_sol->actived_node[i] && G_sol->actived_node[j] && G_sol->E[i][j])
                        H->C[i][j] = 0;
                    else
                        H->C[i][j] = G_problem->C[i][j];
                }
            }

            l_paths = Xp(P_sol, p);
            H->Substract(l_paths); // H = G/Xp
            H->Add(p); // H = p U (G/Xp)
            l_paths->clear();
            delete l_paths;
            p_techo = p;

            Lp = H->GetKPathsBetween(u, v, 1, p->Length() - 1); // busco un solo camino con diametro menor igual al largo del camino que quite
            if (!Lp->empty()) {
                p_techo = Lp->front();
            }

            if (H->CostPath(p_techo) <= G_problem->CostPath(p)) {

                //cout << "p_techo ////////////////////////////////////////////////////" <<endl;
                //PrintPath(p_techo); cout << endl;

                //cout << "888888888888888888888888888" << endl;
                G_sol->Add(p_techo);
                P_sol->Update(p, p_techo);

                //cout << "9999999999999999999999" << endl;
                for (list<int>::iterator it = p_techo->path->begin(); it != p_techo->path->end(); ++it) {
                    if ((*it) != u && (*it) != v && G_sol->GetNodeGrade(*it) > 2) {
                        need_update = true;
                        //cout << "ACTULIZA!!!!!!!!!" << endl;

                        //int entero;
                        //cin >> entero;
                    }
                }
            } else
                G_sol->Add(p);

            DeleteListPath(Lp);
            delete p;
        }
        DeleteListPath(key_path_list);

    }
    delete H;

    return 0;
}

list<int>* restaLista(Graph* G, Graph* H) {
    list<int>* resta = new list<int>;
    for (int i = 0; i < G->sizeG; i++) {
        if (!(H->actived_node[i])) { //FIXME isactive
            resta->push_back(i);
        }
    }
    return resta;
}

int costKTree(list<list<int>*>* kTree, Graph* g) {
    int cost = 0;
    for (list<list<int>*>::iterator it = kTree->begin(); it != kTree->end(); it++) {
        //g->imprimirLista(*it, "Lista del Ktree");
        cost += g->CostListInt(*it);
    }
    return cost;
}
//int costKTreeListPath(list<Path*>* kTree, Graph* g){
//    int cost=0;
//    for(list<list<int>*>::iterator it=kTree->begin(); it!=kTree->end();it++){
//        cost += g->CostPath(*it);
//    }
//    return cost;
//}

void imprimirLista(list<int>* L, const char* mensaje) {
    cout << mensaje << ": ";
    for (list<int>::iterator it = L->begin(); it != L->end(); it++) {
        cout << *it << " ";
    }
    cout << endl;
}

void BusquedaLocal2(Graph * G_problem, Graph *& G_sol, PathMatrix *& P_sol) {
    // cout << "Busqueda local 2 -- sustitución kTree" << endl;
    bool improve = true;
    Graph * H = G_sol;

    while (improve) {
        improve = false;
        list<int>* X = H->getKeyNodes();
        //imprimirLista(X, "Key nodes de H");
        while (!improve && !X->empty()) {
            int v = X->front();
            X->pop_front();
            list<list<int>*>* kTree = H->getKeyTree(v);

            list<int>* Zv = H->auxHojasKTree(kTree); // conjunto de hojas del ktree
            list<int>* Sv = H->auxNodosSteinerKTree(kTree);
            list<int>* Stecho = restaLista(G_problem, H);
            //H->imprimirLista(H->T, "Imprimo nodos terminales de H luego de resta lista (grasp.cpp l435)");
            list<int>* conjNodos = new list<int>(*Stecho);
            conjNodos->push_back(v); // TODO no va v
            conjNodos->insert(conjNodos->begin(), Sv->begin(), Sv->end());
            list<int>* GmenosZv = new list<int>(*conjNodos);
            conjNodos->insert(conjNodos->begin(), Zv->begin(), Zv->end());

            Graph* Gtecho = G_problem->subGrafoInducidoMasAristas(conjNodos, Zv); //se hacen en la siguiente funcion
//            Gtecho->graph_viz("G_techo-generado-LOCAL2");
            //H->imprimirKtree(kTree, "Imprimendo K-Tree ---- 2");

            list<list<int>*>* KTreeBest = new list<list<int>*>(*kTree);
            //list<list<int>*>* KTreeBest= kTree;

            int bestCosto = costKTree(KTreeBest, Gtecho);
            //cout << "Costo best K-tree: " << bestCosto << endl;
            int costoKtree;
            int w = Gtecho->sizeG - 1;
            //iteramos sobre los nodos de steiner que no pertenecen a la solución ni a las hojas del arbol
            for (list<int>::iterator it = GmenosZv->begin(); it != GmenosZv->end(); it++) {
                int s = (int) *it;
                //list<Path*>* Lp=Gtecho->GetKPathsBetween(s,Gtecho->sizeG-1,Zv->size(),Gtecho->diameter);
                list<list<int>*>* Lp = Gtecho->caminoNodoDisjuntos(s, w);
                costoKtree = costKTree(Lp, Gtecho);
                //comparamos con costo optimo
                //H->imprimirLista(H->T, "Imprimo nodos terminales de H");
                if ((costoKtree < bestCosto)&&(H->esFactible())) {
                    //cout << "Mejora!!! :)   Costo era: " << bestCosto << "y paso a ser " << costoKtree << endl;
                    //Gtecho->imprimirKtree(KTreeBest, "El mejor kTree era: ");
                    delete KTreeBest;
                    KTreeBest = new list<list<int>*>(*Lp);
                    //KTreeBest = Lp;
                    //Gtecho->imprimirKtree(KTreeBest, "Y paso a ser: ");
                    bestCosto = costoKtree;
                    improve = true;
                }
            }
            if (improve) {
                //chequeamos solucion 
                //cout << "@@ Cambia el arbol por " << ++contadorCambios << " vez." << endl;
                H->Substract(kTree);
                H->Add(KTreeBest);
            }
        }
    }
    G_sol = H;
}